Routers provided in a communication network, for example, a TCP/IP network, provide a packet forwarding function whereby input data, usually in the form of packets, is switched or routed to a further destination, e.g., along a network link. Typically, as shown in FIG. 1, a data packet 20 is of variable length and comprises, inter alia, a header 25 containing fields or parameters such as, e.g., an Internet protocol (IP) source address 30, where said data originates, and, e.g., an IP destination address 35, where the data is to be routed. Another parameter in the header may include the type of protocol employed, e.g. for IP, TCP (Transmission Control Protocol), UDP, EIGRP, GRP, ICMP, IGMP, IGRP, IP, IPINIP, NOS, OSPF, TCP, RSVP, REST, etc. To perform the forwarding function, as shown in FIG. 2, a router 45 receives a data packet at an input connection 47 and a control mechanism 50 within the router utilizes an independently generated look-up table (not shown) to determine which output link 60 a packet should be routed. It is understood that the packet may first be queued before being routed, and that the forwarding function is performed very fast for high forwarding throughput.
It should be understood that destination (source) addresses may be logical addresses representing one or more logical destination (source) ports as seen by a end host (not shown). Thus, other packet parameter information, whether contained in the header 25 or not, can further include unique physical or interface source port numbers 37 and destination port numbers 39 as shown in FIG. 1. Additional parameters to be found in the header may include, e.g., certain types of data flags (not shown) or, the packet type 41 as shown in FIG. 1, e.g., TCP or IP etc., depending upon the receiver or transmitter application.
Besides the packet forwarding function, the router 45 additionally performs a filtering function. Among the reasons for packet filtering, one is to provide firewall protection so that data or other information is not routed to an improper destination within the network, or, so that the packets do not arrive to those destinations thought to pose, e.g., a security risk. Specifically, to perform packet filtering, the router table is provided with a table or list of rules specifying, e.g., that packets sent from one or more of specified sources are to be prevented from being routed, or, that specific action is to be taken for that packet having a specified source address. Likewise, the filter rules may additionally specify that particular packets destined for a particular destination address should not be forwarded or that other action should be taken before routing that packet. Thus, a variety of filters may be implemented, e.g., those based only on source addresses for a given interface, those based only on destination addresses for a given interface, those based only on source ports for a given interface, those based only on destination ports for a given interface, or those based on any combination of fields.
The filtering rules currently implemented in routers either requiring exact match operation, or be defined in terms of ranges specifying, e.g., the range of source addresses, destination addresses, source/destination port numbers, protocol types, etc., with each rule being applied to every packet that the router receives. That is, for each packet received by the router, every rule is successively applied to ascertain whether that packet is to be forwarded to its indicated destinations or, whether it is to be restricted or re-routed. Implementation of many rules, for example, greater than 500, however, is time consuming and hence, will decrease throughput and compromise quality of service. Thus, to maintain a great level of throughput the filtering function must be performed at very high speeds.
It would be highly desirable to provide a packet filtering mechanism for a router that is capable of performing the filtering operation at high speeds without service degradation.
Further, it would be highly desirable to provide an algorithm for implementation in the router hardware, that provides packet filtering operations at heretofore unattained speeds.